/**
 * 
 */
package dp.passed2;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author michael
Given 6 number, 4 operators and a target number, return true/false (
what is the optimal solution for this?)
 */
public class CanBeExpressed {

	
	public boolean canBeExpressed(int[] A, int target) {
	    int n = A.length;
	    
	    Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();

	    for (int i = 0; i < n; i++) {
	      for (int j = 0; j < n; j++) {
	        map.put(i * n + j, new HashSet<Integer>());
	      }
	    }

	    for (int i = 0; i < n; i++) {
	      map.get(i * n + i).add(A[i]);
	    }

	    for (int len = 1; len < n; len++) {
	      for (int i = 0; i < n - len; i++) {
	        int j = i + len;
	        for (int k = i; k < i + len; k++) {
	  
	          for (Integer i1: map.get(i * n + k)) {
	            for (Integer i2 : map.get((k + 1) * n + j)) {

	              map.get(i * n + j).add(i1 + i2);
	              map.get(i * n + j).add(i1 - i2);
	              map.get(i * n + j).add(i1 * i2);
	              if ( i2!=0 && i1 >= i2 && i1 % i2 == 0 ) {
//	              if (i1 >= i2 && i1 % i2 == 0) {
	                map.get(i * n + j).add(i1 / i2);
	              }
	            }
	          }     

	        }

	      }
	    }

	    //System.out.println(map.get(n - 1));
	    return map.get(n - 1).contains(target);
	}
	
	/**
	 * 
	 */
	public CanBeExpressed() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[] a = {1000, 170, 13, 7, 9, 3};
		int target = 24;
		final CanBeExpressed canBeExpressed = new CanBeExpressed();
		final boolean result = canBeExpressed.canBeExpressed(a, target);
		System.out.println(result);
	}

}
